고차 함수

수학적인 의미를 찾아왔다면 다항함수 문서로

1. 정의2. 주요 용어

2.1. 익명 함수 (Anonymous function)2.2. 일차 함수 (First-order function)

3. 설명 예제

3.1. 함수를 인자로 하여 호출할 수 있는 함수

3.1.1. C++ 구현3.1.2. JavaScript 구현3.1.3. Java 구현

3.2. 함수를 결과로 반환하는 함수

3.2.1. C++ 구현3.2.2. JavaScript 구현3.2.3. Java 구현

3.3. 함수를 인자로 하여 호출할 수 있고 결과로 함수를 반환하는 함수

3.3.1. C++ 구현3.3.2. JavaScript 구현3.3.3. Java 구현

4. 활용 예제

4.1. 수열의 합과 곱에 대한 추상화

4.1.1. 일반적인 구현4.1.2. 1단계 : 함수의 재활용4.1.3. 2단계 : 고차 함수 정의4.1.4. 3단계 : 인자 형식 일반화

4.2. 메르센 수열의 소수 수열 구하기

4.2.1. 일반적인 구현4.2.2. 고차 함수 정의 및 사용

1. 정의 [편집]

어떤 프로그래밍 언어의 함수 구현에서 함수를 인자로 넘길 수 있거나 반환할 수 있을 때 함수를 일급 객체(언어 내부에서 값으로 표현되고 전달될 수 있는 자료형[1])로 취급한다고 하고, 함수를 인자로 받거나 결과로 반환하는 함수를 고차 함수라 한다. 수학의 범함수와 맥락이 비슷하다.

2. 주요 용어 [편집]

2.1. 익명 함수 (Anonymous function) [편집]

별도로 이름을 붙여 정의하거나 변수에 대입되지 않고 함수를 호출하거나 반환할 때 상수 표현식으로 작성된 함수를 말한다. 설명 예제 2의 greeting 함수와 설명 예제 3의 curry 함수가 반환하는 함수가 바로 익명 함수다. 반대로 이름이 있는 함수는 기명 함수라고 한다.[2]

2.2. 일차 함수 (First-order function) [편집]

고차 함수가 아닌 함수를 말한다. 설명 예제 1의 increase 함수와 설명 예제 2의 greeting 함수가 반환하는 함수, 설명 예제 3의 add 함수와 curry 함수가 반환하는 함수는 고차 함수가 아니므로 일차 함수이다.

3. 설명 예제 [편집]

3.1. 함수를 인자로 하여 호출할 수 있는 함수 [편집]

아래의 apply 함수는 함수를 인자로 받을 수 있으므로 고차 함수다.

3.1.1. C++ 구현 [편집]

#include <functional>
#include <iostream>

using namespace std;

int increase(int);
int apply(function<int(int)>, int);

int main(int argc, char **argv)
{
    cout << apply(increase, 9) << endl; // 10

    return 0;
}

int increase(int value)
{
    return value + 1;
}

int apply(function<int(int)> fx, int value)
{
    return fx(value);
}

3.1.2. JavaScript 구현 [편집]

const increase = value => value + 1;
const apply = (fx, value) => fx(value);

console.log(apply(increase, 9)); // 10

3.1.3. Java 구현 [편집]

package wiki.namu.example;

import java.util.function.Function;

public class Main {
	public static final Function<Integer, Integer> INCREASE = value -> value + 1;

	public static void main(String[] args) {
		System.out.println(apply(INCREASE, 9)); // 10
	}

	public static int apply(Function<Integer, Integer> fx, int value) {
		return rx.apply(value);
	}
}

3.2. 함수를 결과로 반환하는 함수 [편집]

아래의 greeting 함수는 결과로 함수를 반환하므로 고차 함수다.

3.2.1. C++ 구현 [편집]

#include <functional>
#include <iostream>
#include <string>

using namespace std;

function<string(const string &)> greeting(const string &);

int main(const int argc, const char **argv)
{
    auto korean_greeting = greeting("안녕");
    auto english_greeting = greeting("Hello");

    cout << korean_greeting("세계") << endl; // 안녕, 세계!
    cout << english_greeting("world") << endl; // Hello, world!

    return 0;
}

function<string(const string &)> greeting(const string &message)
{
    return [message](const string &name) -> string {
        return message + ", " + name + "!";
    };
}

3.2.2. JavaScript 구현 [편집]

const greeting = message => name => `${message}, ${name}!`;
const koreanGreeting = greeting("안녕");
const englishGreeting = greeting("Hello");

console.log(koreanGreeting('세계')); // 안녕, 세계!
console.log(englishGreeting('world')); // Hello, world!

3.2.3. Java 구현 [편집]

package wiki.namu.example;

import java.util.function.Function;

public class Main {
	public static final Function<String, Function<String, String>> GREETING = message -> name -> message + ", " + name + '!';

	public static void main(String[] args) {
		Function<String, String> koreanGreeting = GREETING.apply("안녕");
		Function<String, String> englishGreeting = GREETING.apply("Hello");

		System.out.println(koreanGreeting.apply("세계")); // 안녕, 세계!
		System.out.println(englishGreeting.apply("Hello")); // Hello, world!
	}
}

3.3. 함수를 인자로 하여 호출할 수 있고 결과로 함수를 반환하는 함수 [편집]

다음의 예제는 다변수 함수의 일부 인수를 정적으로 정하는 currying 구현을 나타낸다. 아래의 curry 함수는 함수를 인자로 하여 호출할 수 있고 결과로 함수를 반환하므로 고차 함수다.

3.3.1. C++ 구현 [편집]

#include <functional>
#include <iostream>

using namespace std;

int add(const int &, const int &);
function<int(const int &)> curry(const function<int(const int &, const int &)> &, const int &);

int main(const int argc, const char **argv)
{
    auto add_10 = curry(add, 10);

    cout << add_10(5) << endl; // 15
}

int add(int value_x, int value_y)
{
    return value_x + value_y;
}

function<int(const int &)> curry(const function<int(const int &, const int &)> &fx, const int &value_x) {
    return [fx, value_x](const int &value_y) -> int {
        return fx(value_x, value_y);
    };
}

3.3.2. JavaScript 구현 [편집]

const add = (valueX, valueY) => valueX + valueY;
const curry = (fx, valueX) => valueY => fx(valueX , valueY);
const addTen = curry(add, 10);

console.log(addTen(5)); // = 15

3.3.3. Java 구현 [편집]

package wiki.namu.example;

import java.util.function.Function;
import java.util.function.BiFunction;

public class Main {
	public BiFunction<Integer, Integer, Integer> add = (valueX, valueY) -> valueX + valueY;
	public BiFunction<BiFunction<Integer, Integer, Integer>, Integer, Function<Integer, Integer>> curry = (fx, valueX) -> valueY -> fx.apply(valueX, valueY);

	public static void main(String[] args) {
		Function<Integer, Integer> addTen = curry.apply(add, 10);

		System.out.println(addTen.apply(5)); // 15
	}
}

4. 활용 예제 [편집]

일반적으로 함수형 프로그래밍 패러다임을 지원하는 언어에서는 다양한 고차 함수가 내부적으로 제공되거나 라이브러리로 사용할 수 있도록 되어 있다. 아래에서는 일부 고차 함수를 직접 구현한다.

4.1. 수열의 합과 곱에 대한 추상화 [편집]

고차 함수 fold [3]를 활용한 추상화를 통해 코드의 가독성과 재활용성을 높이는 예제이다.

4.1.1. 일반적인 구현 [편집]

1에서 10까지 정의된 자연수열을 순회하여 합과 곱을 구한다.

#include <array>
#include <iostream>

using namespace std;

int main(const int argc, const char **argv)
{
    const array<const int, 10> sequence = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int summation = 0;
    int production = 1;

    for (const int &i : sequence)
    {
        summation += i;
        production *= i;
    }

    cout << summation << endl; // 55
    cout << production << endl; // 3628800

    return 0;
}

4.1.2. 1단계 : 함수의 재활용 [편집]

합 연산과 곱 연산을 별도의 함수로 만들어 재활용할 수 있게 한다.

#include <array>
#include <iostream>

using namespace std;

template<size_t size>
int get_summation(const array<const int, size> &, const int & = 0);

template<size_t size>
int get_production(const array<const int, size> &, const int & = 1);

int main(const int argc, const char **argv)
{
    const array<const int, 10> sequence = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    cout << get_summation(sequence) << endl; // 55
    cout << get_production(sequence) << endl; // 3628800

    return 0;
}

template<size_t size>
int get_summation(const array<const int, size> &sequence, const int &initial_value)
{
    int result = initial_value;

    for (const int &i : sequence)
    {
        result += i;
    }

    return result;
}

template<size_t size>
int get_production(const array<const int, size> &sequence, const int &initial_value)
{
    int result = initial_value;

    for (const int &i : sequence)
    {
        result *= i;
    }

    return result;
}

4.1.3. 2단계 : 고차 함수 정의 [편집]

별도로 정의한 합 연산과 곱 연산에서 연산자를 제외한 공통된 부분을 고차 함수로 묶는다.

#include <array>
#include <functional>
#include <iostream>

using namespace std;

template<size_t size>
int fold(const array<const int, size> &, const function<int(const int &, const int &)> &, const int &);

int main(const int argc, const char **argv)
{
    const array<const int, 10> sequence = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    auto add = [](const int &value_x, const int &value_y) -> int {
        return value_x + value_y;
    };

    auto multiply = [](const int &value_x, const int &value_y) -> int {
        return value_x * value_y;
    };

    cout << fold(sequence, add, 0) << endl; // 55
    cout << fold(sequence, multiply, 1) << endl; // 3628800

    return 0;
}

template<size_t size>
int fold(const array<const int, size> &sequence, const function<int(const int &, const int &)> &fx, const int &initial_value)
{
    int result = initial_value;

    for (const int &i : sequence)
    {
        result = fx(result, i);
    }

    return result;
}

4.1.4. 3단계 : 인자 형식 일반화 [편집]

이전 단계의 fold 함수는 정수 배열의 연산만 가능했다. 이를 모든 형식에 적용할 수 있게 일반화한다.

#include <array>
#include <functional>
#include <iostream>

using namespace std;

template<class type, class return_type = type, size_t size>
return_type fold(const array<const type, size> &, const function<return_type(const return_type &, const type &)> &, const return_type &);

int main(const int argc, const char **argv)
{
    const array<const int, 10> sequence = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    function<int(const int &, const int &)> add = [](const int &value_x, const int &value_y) -> int {
        return value_x + value_y;
    };

    function<int(const int &, const int &)> multiply = [](const int &value_x, const int &value_y) -> int {
        return value_x * value_y;
    };

    function<function<string(const string &, const int &)>(const string &)> join = [](const string &connector) -> function<string(const string &, const int &)> {
        return [connector](const string &value_x, const int &value_y) -> string {
            return value_x + to_string(value_y) + connector;
        };
    };

    cout << fold(sequence, add, 0) << endl; // 55
    cout << fold(sequence, multiply, 1) << endl; // 3628800
    cout << fold(sequence, join(","), string("")); // 1,2,3,4,5,6,7,8,9,10,

    return 0;
}

template<class type, class return_type, size_t size>
return_type fold(const array<const type, size> &sequence, const function<return_type(const return_type &, const type &)> &fx, const return_type &initial_value)
{
    auto result = initial_value;

    for (const type &i : sequence)
    {
        result = fx(result, i);
    }

    return result;
}

4.2. 메르센 수열의 소수 수열 구하기 [편집]

많은 프로그래밍 언어에서 일반적으로 많이 쓰이는 map[4]과 filter[5]를 구현한다.

4.2.1. 일반적인 구현 [편집]

아래에서는 자연수열을 정적으로 입력하였다. 필요하다면 다른 컨테이너를 사용해 동적으로 임의의 수열을 생성할 수 있다. 메르센 수를 구하는 함수와 소수 판별 함수는 재귀 호출 최적화 및 상황에 따라 컴파일 타임에 값을 연역할 수 있도록 상수 표현식으로 작성되었다. [6]

#include <array>
#include <iostream>
#include <vector>

using namespace std;

constexpr size_t mersenne(const size_t &);
constexpr bool is_prime(const size_t &, const size_t & = 3);

int main(const int argc, const char **argv)
{
    const array<size_t, 10> natural_sequence = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    vector<size_t> mersenne_sequence;
    vector<size_t> prime_sequence;

    for (const auto &i : natural_sequence)
    {
        mersenne_sequence.push_back(mersenne(i));
    }

    for (const auto &i : mersenne_sequence)
    {
        if (is_prime(i))
        {
            prime_sequence.push_back(i);
        }
    }

    for (const auto &i : prime_sequence)
    {
        cout << i << endl; // 3, 7, 31, 127
    }

    return 0;
}

constexpr size_t mersenne(const size_t &n)
{
    return n > 0 ? 2 * mersenne(n - 1) + 1 : 0;
}

constexpr bool is_prime(const size_t &n, const size_t &i)
{
    return n > 1 ? n & 1 ? n % i || i * i > n ? i * i > n ? true : is_prime(n, i + 2) : false : n == 2 : false;
}

4.2.2. 고차 함수 정의 및 사용 [편집]

각 수열을 계산하는 부분을 고차 함수을 이용해 정의하였다.

#include <functional>
#include <iostream>
#include <vector>

using namespace std;
using namespace placeholders;

constexpr size_t mersenne(const size_t &);
constexpr bool is_prime(const size_t &, const size_t & = 3);

template<class type, class return_type = type>
vector<return_type> map(const vector<type> &, const function<return_type(const type &)> &);

template<class type>
vector<type> filter(const vector<type> &, const function<bool(const type &)> &);

int main(int argc, const char **argv)
{
    const vector<size_t> natural_sequence = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    auto mersenne_sequence = map(natural_sequence, function<decltype(mersenne)>(mersenne));
    auto prime_sequence = filter(mersenne_sequence, function<bool(const size_t &)>(bind(is_prime, _1, 3)));

    for (const auto &i : prime_sequence)
    {
        cout << i << endl; // 3, 7, 31, 127
    }

    return 0;
}

constexpr size_t mersenne(const size_t &n)
{
    return n > 0 ? 2 * mersenne(n - 1) + 1 : 0;
}

constexpr bool is_prime(const size_t &n, const size_t &i)
{
    return n > 1 ? n & 1 ? n % i || i * i > n ? i * i > n ? true : is_prime(n, i + 2) : false : n == 2 : false;
}

template<class type, class return_type>
vector<return_type> map(const vector<type> &sequence, const function<return_type(const type &)> &fx)
{
    vector<return_type> mapped;

    for (const type &i : sequence)
    {
        mapped.push_back(fx(i));
    }

    return mapped;
}

template<class type>
vector<type> filter(const vector<type> &sequence, const function<bool(const type &)> &fx)
{
    vector<type> filtered;

    for (const type &i : sequence)
    {
        if (!fx(i))
        {
            continue;
        }

        filtered.push_back(i);
    }

    return filtered;
}

[1] 예를 들면 정수, 실수, 문자, 객체의 주소 등. (언어에 따라 문자열이 포함될 수 있거나 그렇지 않다. 예를 들어 C나 C++에서는 문자열은 문자 배열의 주소이거나 문자 배열을 감싸는 객체의 주소로 나타내기 때문에 문자열 그 자체를 값으로 사용할 수 없으므로 일급 객체가 아니다.)[2] 예를 들면 수학의 삼각함수들이 대표적인 기명 함수다.[3] 자료구조를 접는다고 생각하면 된다.[4] mapping은 자료 구조와 규칙에 따른 계산을 하는 함수를 입력받아 각 항목에 대해 계산된 자료 구조를 반환한다.[5] filtering은 자료 구조와 조건부 처리를 하는 함수를 입력받아 각 항목에 대해 조건부 처리된 자료 구조를 반환한다.[6] C++의 상수 표현식은 인라이닝을 암시하여 인자가 적당히 작을 경우 별도의 함수 구문과 호출 구문을 생성하지 않는다.